package org.example.day04;

import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * <p>  评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示。现给出<span>R</span>行<span>C</span>列的整数数组<span>Cov</span>，每个单元格的数值<span>S</span>即为该栅格的信号质量（已归一化，无单位，值越大信号越好）。<span></span>  </p> <div>  要求从<span>[0, 0]</span>到<span>[R-1, C-1]</span>设计一条最优路测路线。返回该路线得分。 </div> <div>  <p>   规则：  </p>  <div>   1.     路测路线可以上下左右四个方向，不能对角。  </div>  <div>   2.     路线的评分是以路线上信号最差的栅格为准的，例如路径8→4→5→9的值为 4，该线路评分为4。线路最优表示该条线路的评分最高。  </div> </div>
 *
 * 评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示。
 * 现给出R行C列的整数数组Cov，每个单元格的数值S即为该栅格的信号质量（已归一化，无单位，值越大信号越好）。
 * 要求从[0, 0]到[R-1, C-1]设计一条最优路测路线。返回该路线得分。
 * 规则：
 * 1.     路测路线可以上下左右四个方向，不能对角。
 * 2.     路线的评分是以路线上信号最差的栅格为准的，例如路径8→4→5→9的值为 4，该线路评分为4。线路最优表示该条线路的评分最高。
 * @date 2024/3/11 15:21
 */
public class test061 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int R = scanner.nextInt();
        int C = scanner.nextInt();
        int[][] Cov = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                Cov[i][j] = scanner.nextInt();
            }
        }
        int bestRouteScore = bestRouteScore(R, C, Cov);
        System.out.println(bestRouteScore);
    }

    private static boolean isPathFeasible(int[][] Cov, int R, int C, int mid, boolean[][] visited, int x, int y) {
        // DFS 辅助函数，用于检查是否存在一条至少为 mid 信号质量的路径
        // 首先检查当前位置是否合法
        if (x < 0 || x >= R || y < 0 || y >= C || visited[x][y] || Cov[x][y] < mid) {
            return false;
        }

        // 到达终点
        if (x == R - 1 && y == C - 1) {
            return true;
        }

        // 标记当前栅格为已访问
        visited[x][y] = true;

        // 探索四个方向
        if (isPathFeasible(Cov, R, C, mid, visited, x + 1, y) ||
                isPathFeasible(Cov, R, C, mid, visited, x - 1, y) ||
                isPathFeasible(Cov, R, C, mid, visited, x, y + 1) ||
                isPathFeasible(Cov, R, C, mid, visited, x, y - 1)) {
            return true;
        }

        // 回溯
        visited[x][y] = false;
        return false;
    }

    private static int bestRouteScore(int R, int C, int[][] Cov) {
        int left = 0;
        int right = 0;

        // 找到信号质量的可能范围
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                right = Math.max(right, Cov[i][j]);
            }
        }

        // 使用二分查找来确定最大最小值
        while (left < right) {
            int mid = (left + right + 1) / 2; // 向上取整避免死循环
            boolean[][] visited = new boolean[R][C]; // 记录访问状态

            if (isPathFeasible(Cov, R, C, mid, visited, 0, 0)) {
                left = mid; // 存在这样的路径，尝试更大的值
            } else {
                right = mid - 1; // 不存在，降低标准
            }
        }

        return left; // left 和 right 相遇，即为所求
    }
}


